#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct Node{
    // 带头结点
    int data;
    struct Node *next;
}LNode, *LinkList;

// 初始化链表，分配头结点内存
bool InitList(LinkList *L){
    *L=(LinkList)malloc(sizeof(LNode));
    if(*L==NULL){
        return false;
    }
    (*L)->next=NULL;
    return true;
}

// 计算链表长度
int Length(LinkList L){
    int Sum=0;
    LNode *current=L;
    while(current->next!=NULL){
        Sum++;
        current=current->next;
    }
    return Sum;
}

// 根据索引删除节点，并返回被删除节点的数据
bool deleteNodeByIndex(LinkList L,int index,int *e){
    if(Length(L)<index || Length(L)==0){
        return false;
    }
    LNode *current = L;
    for(int i=1;i<index;i++){
        current=current->next;
    }
    *e=current->next->data;
    if(current->next->next==NULL){
        current->next=NULL;
    }
    else{
        LNode *temp =current->next;
        current->next=current->next->next;
        free(temp);
    }
    return true;
}

// 根据值删除节点，并返回被删除节点的信息
bool deleteNodeByValue(LinkList L, int value, LNode *N) {
    if (Length(L) == 0) {
        return false;
    }
    LNode *prev = L;  // 记录前一个节点
    LNode *current = L->next;  // 从第一个有效节点开始遍历

    while (current != NULL) {
        if (current->data == value) {
            *N = *current;  // 复制节点信息
            prev->next = current->next;  // 更新前一个节点的 next 指针
            free(current);  // 释放当前节点的内存
            return true;
        }
        prev = current;  // 更新前一个节点
        current = current->next;  // 移动到下一个节点
    }
    return false;
}

// 根据索引获取节点信息
bool getNodeByIndex(LinkList L,int index,LNode *N){
    if (Length(L) < index || index < 1) {
        return false;
    }
    LNode *current = L;
    for (int i = 0; i < index; i++) {
        current = current->next;
    }
    *N = *current;
    return true;
}

// 根据值获取节点信息
bool getNodeByValue(LinkList L,int value,LNode *N){
    LNode *current = L;
    while (current->next != NULL) {
        current = current->next;
        if (current->data == value) {
            *N = *current;  // 正确复制节点信息
            return true;
        }
    }
    return false;
}

// 在指定索引位置插入节点
bool insertNodeByIndex(LinkList L,int value,int index){
    if (index < 1 || index > Length(L) + 1) {
        return false;
    }
    LNode *newNode = (LinkList)malloc(sizeof(LNode));
    if (newNode == NULL) {
        return false;
    }
    newNode->data = value;
    LNode *current = L;
    for (int i = 1; i < index; i++) {
        current = current->next;
    }
    newNode->next = current->next;
    current->next = newNode;
    return true;
}

// 在链表末尾插入节点
bool insertNode(LinkList L,int value){
    LNode *current = L;
    while (current->next != NULL) {
        current = current->next;
    }
    LNode *newNode = (LinkList)malloc(sizeof(LNode));
    if (newNode == NULL) {
        return false;
    }
    newNode->data = value;
    newNode->next = NULL;
    current->next = newNode;
    return true;
}
void show(LinkList L){
    LNode *current=L;
    while(current->next!=NULL){
        current=current->next;
        printf("%d ",current->data);
    }
    printf("\n");
}

// 新增的测试方法
void testLinkList(LinkList *L) {
    char command[20];
    int data, index, deleted;
    LNode node;
    while (1) {
        printf("请输入操作 (insert/inserti/delete/deletev/get/getv/show/exit): \n");
        scanf("%s", command);

        if (strcmp(command, "insert") == 0) {
            printf("请输入要在链表末尾添加的数据: \n");
            scanf("%d", &data);
            if (insertNode(*L, data)) {
                printf("数据在链表末尾添加成功。\n");
                show(*L);
            } else {
                printf("添加失败。\n");
            }
            // 这里可以添加打印链表的函数，假设名为 printLinkList
            // printLinkList(*L); 
        } else if (strcmp(command, "inserti") == 0) {
            printf("请输入要插入的索引 (从 1 开始) 和数据，以空格分隔: \n");
            scanf("%d %d", &index, &data);
            if (insertNodeByIndex(*L, data, index)) {
                printf("数据在指定索引位置插入成功。\n");
                show(*L);
            } else {
                printf("索引无效或插入失败。\n");
            }
            // printLinkList(*L); 
        } else if (strcmp(command, "delete") == 0) {
            printf("请输入要删除的元素索引 (从 1 开始): \n");
            scanf("%d", &index);
            if (deleteNodeByIndex(*L, index, &deleted)) {
                printf("数据删除成功，删除的数据是: %d\n", deleted);
                show(*L);
            } else {
                printf("索引超出范围，删除失败。\n");
            }
            // printLinkList(*L); 
        } else if (strcmp(command, "deletev") == 0) {
            printf("请输入要删除的值: \n");
            scanf("%d", &data);
            if (deleteNodeByValue(*L, data, &node)) {
                printf("值为 %d 的数据删除成功。\n", data);
                show(*L);
            } else {
                printf("未找到该值，删除失败。\n");
            }
            // printLinkList(*L); 
        } else if (strcmp(command, "get") == 0) {
            printf("请输入要获取的元素索引 (从 1 开始): \n");
            scanf("%d", &index);
            if (getNodeByIndex(*L, index, &node)) {
                printf("索引为 %d 的节点数据是: %d\n", index, node.data);
                show(*L);
            } else {
                printf("索引超出范围，获取失败。\n");
            }
        } else if (strcmp(command, "getv") == 0) {
            printf("请输入要获取的值: \n");
            scanf("%d", &data);
            if (getNodeByValue(*L, data, &node)) {
                printf("值为 %d 的节点数据已获取。\n", data);
                show(*L);
            } else {
                printf("未找到该值，获取失败。\n");
            }
        } else if (strcmp(command, "show") == 0) {
            // printLinkList(*L); 
            show(*L);
        } else if (strcmp(command, "exit") == 0) {
            printf("退出测试。\n");
            break;
        } else {
            printf("无效的操作，请重新输入。\n");
        }
    }
}

int main() {
    LinkList head;
    if (InitList(&head)) {
        testLinkList(&head);
    } else {
        printf("链表初始化失败。\n");
    }
    return 0;
}